1. Field of the Invention
The present invention relates to error detection and/or correction codes.
Error detection codes have a technical effect and solve a significant technical problem. Indeed, they enable restoring the value of one or several erroneous bits, for example, after a storage or a transmission. Without such codes, any storage or transmission of digital data would be difficult.
The present invention relates in particular to linear codes of Hamming type.
2. Discussion of the Related Art
The Hamming code is an error detection and correction code used in many fields. A first example of a Hamming code and its use for the data storage in a memory will be described, in the case where the data to be stored are in the form of 16-bit words.
Let X be the word to be stored. X can be represented by a vector Xe, the 16 components X0 to X15 of which correspond to the 16 bits of the word to be stored. Five error detection bits C1(C0 . . . C4) are obtained by multiplying a parity control matrix H, called a Hamming matrix, of dimensions 5×16, by vector Xe in the form of a column vector.
FIG. 1A illustrates Hamming matrix H for 16 bits and FIG. 1B illustrates the way to obtain the detection bits. Calling hij the elements of matrix H, the error detection bits C1 are given by:
      C    i    =            ∑              j        =        0            15        ⁢                  h        ij            ·              X        j            
Xj being the j-th component of vector Xe.
In write mode, 21-bit words, formed of the 16 data bits Xj and of the 5 detection bits C1, are written into the memory. In read mode, the read word includes 16 bits Xr corresponding to the data bits and 5 bits Cr corresponding to the detection bits. It is possible for Xr and Cr not to be equal to Xj and Ci if errors have occurred between the write and read operations.
To detect and/or correct possible errors on the read bits, a syndrome S with five components S0, . . . S4 is calculated by multiplying a determined matrix H′ of dimensions 5×21 by a column vector with 21 components, including the 16 bits Xr and the 5 bits Cr.
FIG. 2A illustrates matrix H′. The first 16 columns of matrix H′ correspond to the 16 columns of matrix H. The 5 following columns each include a single “1”. The 17-th column has its “1” on the first line, the 18-th column has its “1” on the second line, and so on until the 21rst column, which has its “1” on the fifth line. The last five columns of matrix H′ are used to determine possible errors in the detection bits.
FIG. 2B illustrates the calculation of syndrome S.
If syndrome S has all its components equal to 0, the storage occurs with no error and all the bits of the read word, be they data bits or detection bits, are correct.
If S is different from 0, the read word includes one or several errors. If a single bit of the read word is erroneous, the obtained syndrome enables correcting the error. Indeed, the syndrome corresponds in this case to the column having had its elements multiplied by the erroneous bit. Thus, if the calculated syndrome is equal to:
      S    =          (                                    0                                                0                                                0                                                1                                                1                              )        ,
the components (00011) of the syndrome correspond to the elements of the first column of the Hamming matrix, which means that the first bit, X0, is erroneous.
Similarly, if the calculated syndrome is equal to:
            S      ″        =          (                                    1                                                0                                                0                                                0                                                0                              )        ,
and there is a single error in the read word, this means that the first detection bit C0 is erroneous.
The above-described Hamming code cannot detect two errors. Thus, if an error has occurred on bits X1 and X2, the obtained syndrome is equal to the sum modulo 2 of the syndromes corresponding to errors on X1 and X2, that is, to: S′″=(00101)+(00110)=(00011). The obtained syndrome indicates an error on bit X0, which is wrong.
Indeed, the above Hamming code is known to have a minimum code distance d=3 and a linear code like the Hamming code is known to be able to correct L errors and to detect L+1 errors if its minimum code distance d is strictly greater than 2L+1.
To improve the above code and turn it into a code having a minimum code distance equal to 4, it is known to add to the word to be stored a total parity bit P.
Total parity bit P is calculated by adding modulo 2 all the data bits and all the detection bits. The total parity bit is added to the word to be stored, and the word to be stored, the detection bits, and the total parity bit are altogether stored.
In read mode, the read word is multiplied by parity control matrix H″ shown in FIG. 3A. Matrix H″ has one more line and one more column than matrix H′. Matrix H″ includes, to the top left, that is, on the first five lines and on the first 21 columns, a block identical to matrix H′. The last line D of matrix H″ only includes “1s” and the last line of matrix H″ only includes “0s”, except for the last line.
The obtained syndrome S′ is illustrated in FIG. 3B. Syndrome S′ has six components S0 to S5, and is obtained by multiplying matrix H″ by a column vector including the 22 bits of the read word, formed of the 16 read data bits Xr, followed by the five read detection bits Cr, and by the read total parity bit Pr.
The code thus obtained is a so-called “SEC-DED” code (“Single Error Correction”—“Double Error Detection”). This code has a minimum code distance equal to four and can detect two errors in all cases, two errors being indicated by the fact that the last component of the syndrome, S5, is zero while the syndrome is different from the zero vector. However, the above code has several disadvantages.
Thus, upon coding, the calculation of total parity bit P is required. This calculation requires a large number of adders, since all data bits and detection bits must be added modulo 2. Further, the calculation of the total parity bit cannot be performed in parallel with the calculation of the detection bits, since it requires the previous knowledge of the detection bits. Accordingly, it must be awaited that all detection bits have been calculated to calculate total parity bit P, which wastes time.
Upon decoding, the calculation of the last syndrome component, S5, requires a high number of adders, and the decoding circuit has a low compactness. Further, since each addition lasts for some time, the calculation of the last syndrome component has a relatively long duration and the decoding is not optimal.
It should also be noted that, in the above-described Hamming code, the Hamming matrix is neither symmetrical, nor regular. Thus, considering that the elements of a column correspond to the binary representation of a number, the variation of this number is not regular and includes jumps. This makes difficult the forming of a circuit implementing the Hamming code as well as the syndrome decoding.